class ArrayList {
  constructor(list) {
    this.list = list;
  }
  // 冒泡排序:从头开始，两两对比，遇到大的交换位置
  // 交换次数 O(N²)；比较次数O(N²)
  bubbleSort() {
    //   从外层进行收口
    for (let reduce = this.list.length - 1; reduce >= 0; reduce--) {
      // 进行一轮大小对比
      for (let i = 0; i < reduce; i++) {
        if (this.list[i] > this.list[i + 1]) {
          this.swap(i, i + 1);
        }
      }
    }
    return this.list;
  }
  // 选择排序
  // 交换次数 O(N)；比较次数O(N²)
  selectSort() {
    for (let i = 0; i < this.list.length - 1; i++) {
      let minIndex = i;
      for (let j = minIndex + 1; j < this.list.length; j++) {
        if (this.list[minIndex] > this.list[j]) {
          // 将后边小的移动到前部
          minIndex = j;
        }
      }
      this.swap(minIndex, i);
    }
    return this.list;
  }
  /**
   * @description: 插入排序
   * @param {*}
   * @return {*} 返回被排序后的数据
   */
  insertionSort() {
    for (let i = 1; i < this.list.length; i++) {
      let temp = this.list[i];
      // 定义frontMove变量，不断的寻找要插入temp的位置。
      // 如果出现this.list[frontMove-1]不大于temp，则终止while循环，将temp放入次位置
      let frontMove = i;
      // this.list[frontMove-1]>temp已经排好序的部分，大于要插入的temp，则继续往前查找。
      while (this.list[frontMove - 1] > temp && frontMove > 0) {
        // 此时temp比已排好元素小，把已排好的元素向后移动一位，将frontMove-1的值赋值给frontMove
        this.list[frontMove] = this.list[frontMove - 1];
        frontMove--;
      }
      // 前面排好序号的元素，找到了不大于temp的位置，此时将temp放入该位置
      this.list[frontMove] = temp;
    }
    return this.list;
  }
  /**
   * @description: 希尔排序，该排序是插入排序的升级版，通过几次间隔分组插入排序，可以让元素更接近应该放置的位置
   * @param {*}
   * @return {*}
   */
  shellSort() {
    // 定义将数组划分的间隔，该间隔逐渐减小，直到为1
    let gap = Math.floor(this.list.length / 2);
    while (gap > 0) {
      // 套用插入排序的思想
      for (let i = gap; i < this.list.length; i++) {
        let temp = this.list[i];
        let frontMove = i-gap;
        // 已排序中的值，大于后边的temp，则需要将大的值往后移动一个gap位置
        while (this.list[frontMove] > temp ) {
          this.list[frontMove+gap] = this.list[frontMove];
          // 减小frontMove的值，和前面已经排好序的元素做对比
          frontMove -= gap;
        }
        // 如果this.list[frontMove]已经排好序的元素不大于temp，则此处是temp应该放置的位置
        this.list[frontMove+gap] = temp;
      }
      gap = Math.floor(gap / 2);
    }
    return this.list;
  }
  /**
   * @description: 快速排序
   * @param {*}
   * @return {*}
   */
  quickSort() {
    const quickFn = (arr) => {
      // 快速排序使用了递归，首先需要定义递归的终止条件
      if (arr.length < 2) return arr;
      // 获取数组中间位置的值，作为标志位
      let pivotIndex = Math.floor(arr.length / 2);
      let pivot = arr.splice(pivotIndex, 1)[0];
      // 定义left【加入比标志位小的】数组，right【比标志位大的】数组
      let left = [],
        right = [];
      for (let i = 0; i < arr.length; i++) {
        // 小的放入left数组
        if (arr[i] < pivot) {
          left.push(arr[i]);
        } else {
          // 大的放入right数组
          right.push(arr[i]);
        }
      }
      // 递归调用left和right数组，并且拼接上标志位元素pivot。
      return quickFn(left).concat([pivot], quickFn(right));
    };
    return quickFn(this.list);
  }
  /**
   * @description: 归并排序，也是采用递归以及分治思想，先将数组分成2分，递归下去
   * @param {*}
   * @return {*}
   */
  concatSort() {
    const Sort = (arr) => {
      let len = arr.length;
      if (len < 2) return arr;
      let mid = Math.floor(len / 2);
      let left = arr.slice(0, mid);
      let right = arr.slice(mid);

      const concatFn = (left, right) => {
        const result = [];
        while (left.length > 0 && right.length > 0) {
          // 不断对比左右数组的第一个元素，如果left小，
          // 则将left头部取出放入result，否则取出right头部，使用shift方法，直接将头部元素取出
          result.push(left[0] <= right[0] ? left.shift() : right.shift());
        }
        return result.concat(left, right);
      };
      return concatFn(Sort(left), Sort(right));
    };
    return Sort(this.list);
  }
  swap(x, y) {
    let temp = this.list[x];
    this.list[x] = this.list[y];
    this.list[y] = temp;
  }
}
let arraylist = new ArrayList([9, 5, 1, 54, 23, 89, 6]);
console.log(arraylist.shellSort());
